/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lily
 * Date: 2024-09-25
 * Time: 19:26
 */
public class test_2 {
    static int[] road1 = {1, -1, 0, 0};
    static int[] road2 = {0, 0, 1, -1};
    static int[][] vim;
    static int num;
    static String wo;

    public static boolean exist(String[] board, String word) {
        //开始搜素的位置
        int n = board.length;
        num = word.length();
        wo = word;
        int m = board[0].length();
        char[][] chars = new char[n][m];
        vim = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                chars[i][j] = board[i].charAt(j);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (chars[i][j]==word.charAt(0)) {
                    if(dfs(chars, i, j, 0)) return true;
                }
            }
        }
        return false;
    }

    private static boolean dfs(char[][] chars, int i, int j, int n) {
        if (n == num - 1) {
            return true;
        }
        vim[i][j] = 1;
        for (int k = 0; k < 4; k++) {
            int x = i + road1[k];
            int y = j + road2[k];
            if (x >= 0 && x < chars.length  && y >= 0 && y < chars[0].length && vim[x][y] == 0&&chars[x][y]==wo.charAt(n+1)) {
                if(dfs(chars, x, y, n + 1)) return true;
            }
        }
        vim[i][j]=0;
        return false;
    }

    public static void main(String[] args) {
        String[] arr = {"aa"};
        System.out.println(exist(arr, "aa"));
    }
}
